class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        vector<int> dp(n, 0); // dp[i]表示字符串中[0，i]区间，总编码方法
        dp[0] = (s[0] != '0'); // 题目只有0-9，不等于0就能单独编码
        if(n == 1)
            return dp[0];
 
        if(s[0] != '0' && s[1] != '0') // 两个都能单独编码
            dp[1] += 1;
        int y = (s[0] -'0') * 10 + (s[1] - '0');
        if(y >= 10 && y <= 26) // 和在一起能编码，不含前导0
            dp[1] += 1;
 
        for(int i = 2; i < n; ++i)
        {
            if(s[i] != '0') // 能单独编码
                dp[i] += dp[i-1];
 
            y = (s[i-1] -'0') * 10 + (s[i] - '0');
            if(y >= 10 && y <= 26) // 和在一起能编码，不含前导0
                dp[i] += dp[i-2];
        }
        return dp[n-1];
    }
};